package com.future;

/**
 * Description: 32. ���Ч���ţ���ˢ���14��
 * ����һ��ֻ���� '('?�� ')'?���ַ������ҳ����Ч����ʽ��ȷ�������������Ӵ��ĳ��ȡ�
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺s = "(()"
 * �����2
 * ���ͣ����Ч�����Ӵ��� "()"
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/longest-valid-parentheses
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/4/28 10:01
 */
public class Solution_32 {

    public static void main(String[] args) {
        String s = ")()())";
        //s = "((()())())";
        System.out.println(longestValidParentheses(s));
    }

    /**
     * @param s
     * @return
     */
    public static int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int N = s.length();
        /**
         * dp[i],��ʾ��ǰ�±�Ϊi���ճɵ��������Ч���ŵĳ���
         */
        int dp[] = new int[N];
        dp[0] = 0;
        int ans = 0;
        for (int i = 1; i < N; i++) {
            if (s.charAt(i) == ')') {
                /**
                 * �ҵ�ǰһ����')'ƥ���'('
                 */
                int pre = i - dp[i - 1] - 1;
                if (pre >= 0 && s.charAt(pre) == '(') {
                    /**
                     *
                     *
                     * 1�����i-1��'('����ôdp[i-1]=0,��iǡ�ôճ�һ�ԣ�����Ϊ2
                     * eg:"()"��������λ��1
                     * ......
                     *
                     */
                    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                    ans = Math.max(dp[i], ans);
                }
            }
        }
        return ans;
    }
}
